School of Computer Engineeringcoretheory

DESIGN AND ANALYSIS OF ALGORITHMS

CSS 2202

Syllabus

01Fundamentals of Algorithms
02Important Problem Types
03Analysis of algorithm efficiency
04Analysis Framework: Asymptotic Notations and Basic Efficiency Classes
05Mathematical Analysis of Non-recursive and Recursive Algorithms
06Brute force Techniques
07Divide and Conquer
08Decrease and Conquer: Insertion Sort, Depth First Search, Breadth First Search, Topological Sorting
09Transform and Conquer: Presorting, BST, Heapsort
10Space and Time tradeoffs: Input Enhancement in String Matching
11Dynamic Programming: Warshall's and Floyd's Algorithms, The Knapsack Problem
12Greedy Techniques: Prim's, Kruskal's and Dijkstra's Algorithm, Huffman Trees
13Coping with limitations of algorithmic power, P, NP, and NP-complete Problems
14Backtracking: n–Queens problem, Hamiltonian Circuit Problem, Subset–Sum Problem
15Branch and Bound: Assignment Problem, Knapsack Problem, TSP

Anany Levitin, Introduction to the Design and Analysis of Algorithms, (3e), Pearson Education, 2017
Ellis Horowitz and Sartaj Sahni, Computer Algorithms/C++, (2e), University Press, 2007
Thomas H. Cormen, Charles E. Leiserson, Ronal L, Rivest, Clifford Stein, Introduction to Algorithms, (2e), PHI, 2006
Kleinberg, Jon, and Tardos, Éva. Algorithm Design. United Kingdom, Pearson, 2013
https://archive.nptel.ac.in/courses/106/105/106105164/

Credits Structure

3Lecture

1Tutorial

0Practical

4Total